package sort.quicksort;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.Executors;

/**
 * @author XY
 * @version 1.0
 * @date 2021/9/13 11:10
 * @Description
 */
public class QuickSort {

    private QuickSort(){

    }

    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr,0,arr.length-1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr,int l,int r){

        if(l>=r){
            return;
        }
//        if(r-l<=15){
//
//        }
        int partition = partition(arr, l, r);
        sort(arr,l,partition-1);
        sort(arr,partition+1,r);

    }

    private static <E extends Comparable<E>> int partition(E[] arr,int l,int r){
        //增加随机化，避免遇到有序数组排序时间过长
        int p = l+new Random().nextInt(r-l+1);
        swap(arr,l,p);
        int i = l;
        for (int j = l+1; j <= r; j++) {
            if(arr[j].compareTo(arr[l])<0){
                i++;
                E temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        E t=arr[i];
        arr[i] = arr[l];
        arr[l] = t;
        return i;

    }

    //双路排序算法
    public static <E extends Comparable<E>> void sort2ways(E[] arr){
        sort2ways(arr,0,arr.length-1);
    }

    private static <E extends Comparable<E>> void sort2ways(E[] arr,int l,int r){

        if(l>=r){
            return;
        }
//        if(r-l<=15){
//
//        }
        int partition = partition2(arr, l, r);
        sort2ways(arr,l,partition-1);
        sort2ways(arr,partition+1,r);

    }

    //双路快速排序
    private static <E extends Comparable<E>> int partition2(E[] arr,int l,int r){
        //增加随机化，避免遇到有序数组排序时间过长
        int p = l+new Random().nextInt(r-l+1);
        swap(arr,l,p);
        int i = l+1,j=r;
        while(true){
            while(i<=j && arr[i].compareTo(arr[l])<0){
                i++;
            }
            while(j>=i && arr[j].compareTo(arr[l])>0){
                j--;
            }
            if(i>=j){
                break;
            }
            swap(arr,i,j);
            i++;
            j--;
        }
        swap(arr,l,j);
        return j;
    }

    //三路快速排序
    public static <E extends Comparable<E>> void sort3ways(E[] arr){
        sort3ways(arr,0,arr.length-1);
    }

    private static <E extends Comparable<E>> void sort3ways(E[] arr,int l,int r){


        if(l>=r){
            return;
        }
        int p = l+new Random().nextInt(r-l+1);
        swap(arr,l,p);
        //arr[l+1,lt]<v arr[lt+1,i-1]==v ,arr[gt,r]>v
        int lt = l, i=l+1, gt=r+1;
        while(i < gt){
            if(arr[i].compareTo(arr[l])<0){
                lt++;
                swap(arr,i,lt);
                i++;
            }else if(arr[i].compareTo(arr[l])>0){
                gt--;
                swap(arr,i,gt);
            }else{
                i++;
            }
        }
        swap(arr,l,lt);
        sort3ways(arr,l,lt-1);
        sort3ways(arr,gt,r);

    }

    private static <E extends Comparable<E>> void swap(E[] arr,int a,int b){
        E temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3};
        arr[0] = arr[0]^arr[1];
        System.out.println(arr[0]);
        arr[1] = arr[0]^arr[1];
        System.out.println(arr[1]);
        arr[0] = arr[0]^arr[1];
        System.out.println(arr[0]);
//        Arrays.stream(arr).forEach(System.out::println);
    }
}
